public class HashBuck {
    //节点
    static class Node {
        public int key;
        public int value;
        public Node next;

        public Node(int key,int value) {
            this.key = key;
            this.value = value;
        }
    }
    //哈希桶是一个节点数组，所以我们使用节点来创建一个数组
    public Node[] array = new Node[10];
    //有效的数据长度
    public int usedSize;

    //负载因子
    public static final double DEFAULT_LOAD_FACTOR = 0.75f;

    //插入元素
    public void put(int key,int value) {
        //计算地址
        int index = key % array.length;

        //检查是否出现相同的 key 值
        Node cur = array[index];
        while (cur != null) {
            if (cur.key == key) {
                cur.value = value;
                return;
            }
            cur = cur.next;
        }

        //如果没有key值的话，使用头插法把新的节点插入到 哈希表中
        Node newNode = new Node(key,value);
        newNode.next = array[index];
        array[index] = newNode;

        //插入之后有效长度增加
        usedSize++;

        //判断负载因子
        if (loadFactor() >= DEFAULT_LOAD_FACTOR) {
            //扩容
            resize();
        }
    }

    private void resize() {

        Node[] newarray = new Node[2 * array.length];
        for (int i = 0; i < array.length; i++) {
            Node cur = array[i];
            while (cur != null) {
                int newindex = cur.key % newarray.length;
                Node curN = cur.next;
                cur.next = newarray[newindex];
                newarray[newindex] = cur;
                cur = curN;
            }
        }

        array = newarray;
    }

    //计算负载因子
    private double loadFactor() {
        return usedSize * 1.0 / array.length;
    }

    //根据传入的 key 查找到所对应的 value 值
    public int getVal(int key) {
        int index = key % array.length;
        Node cur = array[index];
        while(cur != null) {
            if (cur.key == key) {
                return cur.value;
            }
            cur = cur.next;
        }

        return -1;
    }
}
